import com.sun.source.tree.WhileLoopTree;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wulangaaa
 * Date: 2025-04-19
 * Time: 14:29
 */
public class MyBTree {
    class BTreeNode{
        int[] keys;//存放数据
        BTreeNode[] subs;//存放孩子节点的地址
        BTreeNode parent;//分裂时候需要拿某个数据向上插入，增加一个parent方便后续找到父亲节点并插入
        int size;// 记录当前节点的关键字数
       //带参数的构造方法也可以
       //就是可以手动指定是几阶的这样一个B树
        public BTreeNode(int M) {
            this.keys = new int[M];//多加一个空间
            this.subs = new BTreeNode[M+1];//孩子节点数总要比存的数据key值多一个
            this.size =0;
        }
        //不带参构造方法
        private  static  final int  DEFAULT_CAPACITY=3;
        public BTreeNode(){
            this.keys = new int[DEFAULT_CAPACITY];//多加一个空间
            this.subs = new BTreeNode[DEFAULT_CAPACITY+1];
            this.size =0;
        }

    }
    BTreeNode root;

    //插入方法
    public  boolean insert(int key){
        //b树本来就是空的
        if (root==null){
            //直接插入即可
            root=new BTreeNode();
            root.keys[0]=key;
            root.size++;
            return true;
        }

        //b树不为空，正常插入
        //判断key是否已经存在
        pari<BTreeNode,Integer> parent=findKey(key);
        BTreeNode parent1 =parent.getKey();
        if (parent.getVal()<0){
            //-1是小于零的----没找到
            //比较排序插入
            int index=parent1.size-1;//先更最大的也就是index位置处的数比
            while (index>=0){
                if (parent1.keys[index]>=key){
                    parent1.keys[index+1]=parent1.keys[index];
                    index--;
                }else {
                    parent1.keys[index+1]=key;
                    break;
                }
            }
            parent1.keys[index+1]=key;
            parent1.size++;
            //开始判满 如果满了就需要分裂
            if (parent1.size<parent1.keys.length){
                //没满
                return true;
            }else {
                //满了就需要分裂
            split(parent1);
            return true;
            }


        }else {
            //找到了 val=1- 不能插入
            System.out.println("key值已有，插入失败");
            return false;
        }


    }

    private void split(BTreeNode parent1) {

        //无论处理根还是非根，都需要右边new一个节点
        BTreeNode newNode=new BTreeNode();
        int mid=parent1.size>>1;
        int midth=parent1.keys[mid];
        //将mid右边的拷到右边新new的节点中
        int i=mid+1,j=0;


        //情况1：分裂根节点情况，就是分裂root的情况 需要多在上面new一个节点

        if (parent1==root){
            root=new BTreeNode();
            root.keys[0]=midth;
            root.subs[0]=parent1;
            root.subs[1]=newNode;
            for (;i<parent1.size;i++){
                newNode.keys[j]=parent1.keys[i];
                newNode.subs[j]=parent1.subs[i];
                //修改父亲节点
                if (parent1.subs[i]!=null) {
                    parent1.subs[i].parent = newNode;
                }
                newNode.size++;
                j++;
            }
            //手动将最后一个孩子节点地址移到右边去
            newNode.subs[j]=parent1.subs[i];
            if (parent1.subs[i]!=null) {//修改孩子节点的父亲节点
                parent1.subs[i].parent = newNode;
            }
            root.size++;
            parent1.parent=root;
            newNode.parent=root;
            parent1.size=parent1.size-1-newNode.size;
            return;
        }

        //情况2：分裂非根情况：包括叶子节点和非root的根节点，就是子树的根节点，其实情况2也可以分为两种：叶子节点和非root根节点，但是非root根
        //节点的代码对叶子节点情况也是通用的，所以合二为一了；
        //步骤1:处理右节点
        BTreeNode parent=parent1.parent;//parent绝对不为null因为处理的都是非root的节点，一定会有一个上面节点
        //1.1将mid右边的拷到右边新new的节点中
        //这段代码对有孩子和没孩子的节点都是通用的
        for (;i<parent1.size;i++){
            newNode.keys[j]=parent1.keys[i];
            //管左边
            newNode.subs[j]=parent1.subs[i];
            //修改孩子的父亲节点
            if (parent1.subs[i]!=null) {//处理叶子时候，没有孩子
                parent1.subs[i].parent = newNode;
            }
            newNode.size++;
            j++;
        }
        //手动后将最右边的孩子节点拷贝到新new的节点中
        newNode.subs[j]=parent1.subs[i];
        if (parent1.subs[i]!=null) {
            parent1.subs[i].parent = newNode;
        }
        newNode.parent=parent;
        parent1.size=parent1.size-1-newNode.size;
        // 开始处理根之前


        //开始处理父亲节点
        //先比较排序插入合适位置
        int index=parent.size-1;
        for (;index>=0;index--){
            if (parent.keys[index]>=midth){
                parent.keys[index+1]=parent.keys[index];
                //改动孩子
                //就是只需要将key的右孩子跟着往后挪可以,最左边不用动，然后在index+2处赋上新new的节点的地址即可
                //每个key值管理一个右孩子，key动了，管理的孩子也要动
                parent.subs[index+2]=parent.subs[index+1];

            }else break;

        }
        parent.keys[index+1]=midth;
        parent.subs[index+2]=newNode;
        parent.size++;
        //还需要判断一下叶子节点的上面的节点在加入我们的mid之后是否也满了
        if (parent.size>=parent1.keys.length){
            //如果满了就需要递归继续分裂该节点
            split(parent);
        }
    }

    /**
     *可以弄一个pair型来区分是找到还是没找到，不然纯一个地址无法区分
     * 寻找key
     * @param key
     * @return
     */
    private pari<BTreeNode,Integer> findKey(int key) {
        BTreeNode cur=root;
        BTreeNode parent=null;
        while (cur!=null){
            int i=0;
            while (i < cur.size) {
                if (cur.keys[i]>key){
                    break;
                }else if (cur.keys[i]==key){
               //找到了
                    return new pari<>(cur,1);

                }else {
                    i++;
                }
            }
            parent=cur;
            cur=cur.subs[i];
        }
        //没找到 直接放回要插入key的位置，避免后续再去找
        return new pari<>(parent,-1);
    }

    public static void main(String[] args) {
        MyBTree myBtree = new MyBTree();
        int[] array = {53, 139, 75, 49, 145, 36,101};
        for (int i = 0; i < array.length; i++) {
            myBtree.insert(array[i]);
        }
        myBtree.inorder(myBtree.root);
    }

    private void inorder(BTreeNode root){
        if(root == null)
            return;
        for(int i = 0; i < root.size; ++i){
            inorder(root.subs[i]);
            System.out.print(root.keys[i]+" ");
        }
        inorder(root.subs[root.size]);
    }

}
